import java.util.Arrays;

public class Dijkstra {
    /**
     * 最短路径
     */
    public static void main(String[] args) {
        int MAX = 65535;
        int[][] G = {{0, 1, 5, MAX, MAX, MAX, MAX, MAX, MAX},
                {1, 0, 3, 7, 5, MAX, MAX, MAX, MAX},
                {5, 3, 0, MAX, 1, 7, MAX, MAX, MAX},
                {MAX, 7, MAX, 0, 2, MAX, 3, MAX, MAX},
                {MAX, 5, 1, 2, 0, 3, 6, 9, MAX},
                {MAX, MAX, 7, MAX, 3, 0, MAX, 5, MAX},
                {MAX, MAX, MAX, 3, 6, MAX, 0, 2, 7},
                {MAX, MAX, MAX, MAX, 9, 5, 2, 0, 4},
                {MAX, MAX, MAX, MAX, MAX, MAX, 7, 4, 0}};
        Dijkstra(G, 0);
    }

    public static void Dijkstra(int[][] G, int v0){
        int len = G.length;
        int[] path = new int[len];
        boolean[] finish = new boolean[len];   // 表示已求得v0 与vi间的最小距离
        int[] distance = Arrays.copyOf(G[v0],len);
        finish[v0] = true;
        int min;
        for (int i = 1; i < len; i++) {
            min = 65535;
            int k = 0;
            for (int j = 0; j < len; j++) {
                if (!finish[j] && distance[j] < min){
                    k = j;
                    min = distance[j];
                }
            }
            finish[k] = true;
            for (int j = 0; j < len; j++) {
                if (!finish[j] && min + G[k][j] < distance[j]){
                    distance[j] = min + G[k][j];
                    path[j] = k;
                }
            }
        }
        System.out.println("路径" + Arrays.toString(path));
        System.out.println("距离" + Arrays.toString(distance));
        System.out.println(Arrays.toString(finish));
    }
}
